import collections
import functools
from copy import copy
from typing import List


class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        # 判断target中是否有stickers中没有的字母：无法构成的情况
        set1 = set()
        for sticker in stickers:
            set1 |= set(sticker)
        set2 = set(target)
        if len(set2 - set1) > 0:
            return -1

        # 整理贴纸，剔除不存在于target中的字母
        clear_stickers = []
        for sticker in stickers:
            count = collections.Counter()
            for ch in sticker:
                if ch in set2:
                    count[ch] += 1
            if count:
                clear_stickers.append(count)
        # print(clear_stickers, target)

        size1 = len(clear_stickers)
        size2 = len(target)

        @functools.lru_cache(None)
        def dfs(stat1):
            if stat1 == 0:
                return 0

            # 找到还存在的最后一个字符
            idx = size2 - (stat1 & (-stat1)).bit_length()  # lowbit
            aim = target[idx]

            # print("DFS状态:", bin(stat1)[2:], "->", aim, [idx])

            # 遍历寻找最优解
            ans = 16
            for i in range(size1):
                if aim in clear_stickers[i]:
                    # 计算使用当前词后的新状态
                    stat2 = stat1
                    count2 = copy(clear_stickers[i])
                    for j in range(size2):
                        # print(j, target[-j - 1], stat2 & (1 << j), count2[target[-j - 1]])
                        if stat2 & (1 << j) and count2[target[-j - 1]] > 0:
                            count2[target[-j - 1]] -= 1
                            stat2 ^= (1 << j)

                    # print("DFS", bin(stat1)[2:], "->", bin(stat2)[2:], clear_stickers[i])

                    # 递归求值
                    ans = min(ans, dfs(stat2))
            return ans + 1

        return dfs((1 << size2) - 1)


if __name__ == "__main__":
    print(Solution().minStickers(["with", "example", "science"], "thehat"))  # 3
    print(Solution().minStickers(["notice", "possible"], "basicbasic"))  # -1

    # 测试用例21/101
    print(Solution().minStickers(["fly", "me", "charge", "mind", "bottom"], "centorder"))  # 4

    # 测试用例32/101 : 3
    print(Solution().minStickers(
        ["control", "heart", "interest", "stream", "sentence", "soil", "wonder", "them", "month", "slip", "table",
         "miss", "boat", "speak", "figure", "no", "perhaps", "twenty", "throw", "rich", "capital", "save", "method",
         "store", "meant", "life", "oil", "string", "song", "food", "am", "who", "fat", "if", "put", "path", "come",
         "grow", "box", "great", "word", "object", "stead", "common", "fresh", "the", "operate", "where", "road",
         "mean"], "stoodcrease"))
